package leetcode_61_80;

public class uniquePaths_62 {
    /**
     * 一个机器人位于一个 m x n 网格的左上角
     * 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角
     * 问总共有多少条不同的路径
     */
    public int uniquePaths(int m, int n) {
        /**
        思路是递归回溯法
        太慢了，直接超时，存在很多冗余计算
         */
        int row=0,col=0;
        return function(m,n,row,col);
    }
    public int function(int m, int n,int row,int col){
        if(m-1==row||col==n-1){               //行或者列到底后，到达终点，就只剩一种走法，直接返回1即可
            return 1;
        }
        return function(m,n,row+1,col)+function(m,n,row,col+1);
    }

    /**
     * 尝试动态规划
     * 从右下角开始计算
     * 用一二维数组计算每个格子走到终点的路径
     *0ms ,100%,开心
     */
    public int uniquePaths2(int m, int n) {
        int [][] dp=new int[m][n];
        //初始化最后一行最后一列，这些格子到达终点都只有一种路径
        for(int i=0;i<m;i++)
            dp[i][n-1]=1;
        for(int i=0;i<n;i++)
            dp[m-1][i]=1;
        for(int i=m-2;i>=0;i--){   //行
            for(int t=n-2;t>=0;t--){  //列
                dp[i][t]=dp[i+1][t]+dp[i][t+1]; //每次只能向下或者向右移动一步
            }
        }
        return dp[0][0];
    }
}
